package 抽象数据类型;

import java.util.LinkedList;
import java.util.Queue;

public class AVLTreeNode {
    int data;
    int height;
    AVLTreeNode left;
    AVLTreeNode right;

    public int getData() {
        return data;
    }

    public AVLTreeNode(int data) {
        this.data = data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public int getHeight() {
        return height;
    }

    public void setHeight(int height) {
        this.height = height;
    }

    public AVLTreeNode getLeft() {
        return left;
    }

    public void setLeft(AVLTreeNode left) {
        this.left = left;
    }

    static int Height(AVLTreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(Height(root.getLeft()) + 1, Height(root.getRight()) + 1);
    }

    public AVLTreeNode getRight() {
        return right;
    }

    public void setRight(AVLTreeNode right) {
        this.right = right;
    }

    AVLTreeNode singleRotateLeft(AVLTreeNode notBlancedNode) {
        AVLTreeNode movedNode = notBlancedNode.getLeft();
        notBlancedNode.setLeft(movedNode.getRight());
        movedNode.setRight(notBlancedNode);
        notBlancedNode.setHeight(Height(notBlancedNode));
        movedNode.setHeight(Height(movedNode));
        return movedNode;
    }

    AVLTreeNode singleRotateRight(AVLTreeNode notBlancedNode) {
        AVLTreeNode movedNode = notBlancedNode.getRight();
        notBlancedNode.setRight(movedNode.getLeft());
        movedNode.setLeft(notBlancedNode);
        notBlancedNode.setHeight(Height(notBlancedNode));
        movedNode.setHeight(Height(movedNode));
        return movedNode;
    }

    AVLTreeNode doubleRotateWithLeft(AVLTreeNode notBlancedNode) {
        notBlancedNode.setLeft(singleRotateRight(notBlancedNode.getLeft()));
        return singleRotateLeft(notBlancedNode);
    }

    AVLTreeNode doubleRotateWithRight(AVLTreeNode notBlancedNode) {
        notBlancedNode.setRight(singleRotateLeft(notBlancedNode.getRight()));
        return singleRotateRight(notBlancedNode);
    }

    AVLTreeNode insert(AVLTreeNode root, AVLTreeNode parent, int data) {
        if (root == null) {
            root = new AVLTreeNode(data);
            root.setHeight(Height(root));
        } else if (data < root.getData()) {
            root.setLeft(insert(root.getLeft(), root, data));
            if ((Height(root.getLeft()) - Height(root.getRight())) == 2) {
                if (data < root.getData()) {
                    root = singleRotateLeft(root);

                } else {
                    root = doubleRotateWithLeft(root);
                }
            }
        } else if (data > root.getData()) {
            root.setRight(insert(root.getRight(), root, data));
            if ((Height(root.getRight()) - Height(root.getLeft())) == 2) {
                if (data < root.getData()) {
                    root = singleRotateRight(root);
                } else {
                    root = doubleRotateWithRight(root);
                }
            }
        }
        root.setHeight(Height(root));
        return root;
    }

    public static void LevelOrderTravers(AVLTreeNode treeNode) {
        Queue queue = new LinkedList<AVLTreeNode>();
        queue.add(treeNode);
        int count;
        int depth = 0;
        while (!queue.isEmpty()) {
            count = queue.size();
            while (count-- > 0) {
                AVLTreeNode remove = (AVLTreeNode) queue.remove();
                System.out.println(remove.getData());
                if (remove.getLeft() != null) {
                    queue.add(remove.getLeft());

                }
                if (remove.getRight() != null) {
                    queue.add(remove.getRight());
                }
            }
            depth++;
        }
    }


    public static void main(String[] args) {
        AVLTreeNode root = new AVLTreeNode(4);
        root.left = new AVLTreeNode(2);
        root.right = new AVLTreeNode(7);
      /*  root.left.left = new AVLTreeNode(4);
        root.left.right = new AVLTreeNode(5);*/
        root.right.left = new AVLTreeNode(5);
        root.right.right = new AVLTreeNode(8);
        /* root.right.right.right = new AVLTreeNode(8);*/
        //root.right.right.left = new AVLTreeNode(5);
        // root.right.right.right.left.right= new AVLTreeNode(19);

        System.out.println(Height(root));
        LevelOrderTravers(root.insert(root, null, 6));
    }

}
